package main

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}
	queue := []*TreeNode{}
	tempQueue := []*TreeNode{}
	queue = append(queue, A)
	for i := 0; i < len(queue); i++ {
		if queue[i].Val == B.Val {
			tempQueue = append(tempQueue, queue[i])
		}
		if queue[i].Left != nil {
			queue = append(queue, queue[i].Left)
		}
		if queue[i].Right != nil {
			queue = append(queue, queue[i].Right)
		}
	}
	if len(tempQueue) == 0 {
		return false
	}
	for i := 0; i < len(tempQueue); i++ {
		tempA := tempQueue[i]
		tempB := B
		queueA := []*TreeNode{}
		queueB := []*TreeNode{}
		queueA = append(queueA, tempA)
		queueB = append(queueB, tempB)
		for i := 0; i < len(queueB); i++ {
			if queueB[i].Val != queueA[i].Val {
				break
			}
			if queueB[i].Left != nil {
				queueB = append(queueB, queueB[i].Left)
				if queueA[i].Left == nil {
					break
				}
				queueA = append(queueA, queueA[i].Left)
			}
			if queueB[i].Right != nil {
				queueB = append(queueB, queueB[i].Right)
				if queueA[i].Right == nil {
					break
				}
				queueA = append(queueA, queueA[i].Right)
			}
		}
		if len(queueA) != len(queueB) {
			continue
		}
		for i := 0; i < len(queueB); i++ {
			if queueB[i].Val != queueA[i].Val {
				break
			}
			if i == len(queueB)-1 {
				return true
			}
		}
	}
	return false
}

func main() {
	node4 := &TreeNode{Val: 4}
	node3 := &TreeNode{Val: 3}
	node2 := &TreeNode{Val: 2}
	node1 := &TreeNode{Val: 1}
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4

	node5 := &TreeNode{Val: 3}
	structure := isSubStructure(node1, node5)
	println(structure)
}
